/*
 * Heuristic.cpp
 *
 *  Created on: May 26, 2012
 *      Author: hugo
 */

#include "Heuristic.h"
#include "LocalSol.h"
#include <sys/resource.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>

int compare (const void * a, const void * b)
{
  return ( (*(Vertex*)b).get_prize() - (*(Vertex*)a).get_prize() );
}

void Tempo_CPU_Sistema(double *seg_CPU_total, double *seg_sistema_total)
{
  long seg_CPU, seg_sistema, mseg_CPU, mseg_sistema;
  struct rusage ptempo;

  getrusage(0,&ptempo);

  seg_CPU = ptempo.ru_utime.tv_sec;
  mseg_CPU = ptempo.ru_utime.tv_usec;
  seg_sistema = ptempo.ru_stime.tv_sec;
  mseg_sistema = ptempo.ru_stime.tv_usec;

 *seg_CPU_total     = (seg_CPU + 0.000001 * mseg_CPU);
 *seg_sistema_total = (seg_sistema + 0.000001 * mseg_sistema);
}

Heuristic::Heuristic(Instance *_instance) {
	instance = _instance;
	best=NULL;
	e_null=NULL;
	seed=1;
	stddev=0;
}

double Heuristic::get_stddev(){
	return stddev;
}
pair<float,Edge*> Heuristic::eval_node(Vertex *vertex, int depth){
	Solution *sol=NULL;
	return eval_node(vertex,depth,sol);
}

pair<float,Edge*> Heuristic::eval_node(Vertex *vertex, int depth,Solution* sol){
	if(depth==0)return make_pair(0,e_null);
	float val=0;
	Edge *best_e=NULL;
	for(long i=0;i<instance->num_vertex();i++){
		Edge *e = instance->get_edge(vertex->get_id(),i);
		float tmp;
		if(e!=NULL && !e->is_locked()){
			tmp = vertex->get_prize()/e->get_cost();

			Vertex* n;
			if(vertex->get_id()!=e->get_i())
				n = instance->get_vertex(e->get_i());
			else
				n = instance->get_vertex(e->get_j());

			if(sol==NULL || !sol->has_vertex(n)){
				e->lock();
				tmp+=eval_node(n,depth-1).first;
				e->unlock();

				if(tmp>val){
					val=tmp;
					best_e = e;
				}
			}
		}
	}
	return make_pair(val,best_e);
}

void Heuristic::build(Solution *sol, int depth){
	pair<float,Edge*> tmp1,tmp2,best=make_pair(0,e_null);
	for(int i=0;i<sol->size();i++){
		Edge *e = sol->get_edge(i);
		Vertex *n1 = instance->get_vertex(e->get_i());
		Vertex *n2 = instance->get_vertex(e->get_j());
		tmp1 = eval_node(n1,depth,sol);
		tmp2 = eval_node(n2,depth,sol);

		if(tmp1.first>best.first)
			best=tmp1;
		if(tmp2.first>best.first)
			best=tmp2;
	}
	if(best.second!=NULL && sol->is_better(best.second)){
		best.second->lock();
		sol->add_edge(best.second);
		build(sol,depth);
	}
}

Solution* Heuristic::search(int depth){
	Solution *sol = new Solution(instance);
	Vertex *start_v=NULL;
	Edge *start_e=NULL;
	float val=0;
	for(int i=0;i<instance->num_vertex();i++){
		Vertex *tmp_v = instance->get_vertex(i);
		pair<float,Edge*> tmp = eval_node(tmp_v,depth);
		if(tmp.first>val || start_v==NULL){
			start_v = tmp_v;
			val = tmp.first;
			start_e = tmp.second;
		}
	}

	start_e->lock();
	sol->add_edge(start_e);

	build(sol,depth);

	return sol;
}

vector<Edge*> Heuristic::build_pool(unsigned int length){
	int worst=-1;
	vector<Edge*> pool;
	//cout<<"building pool..."<<endl;
	for(int i=0;i<instance->num_vertex();i++){
		for(int j=i;j<instance->num_vertex();j++){
			Edge *e = instance->get_edge(i,j);
			if(e!=NULL){
				if(pool.size()<length){
					pool.push_back(e);
					if(worst==-1 || instance->compare_edges(e,pool.at(worst))==-1){
						worst=pool.size()-1;
					}
				}else{
					if(worst!=-1 && instance->compare_edges(e,pool.at(worst))==1){
						pool.erase(pool.begin()+worst);
						pool.push_back(e);
						worst=0;
						for(unsigned int k=1;k<pool.size();k++){
							if(instance->compare_edges(pool.at(worst),pool.at(k))==1){
								worst=k;
							}
						}
					}
				}
			}
		}
	}
	//cout<<"ok"<<endl;
	return pool;
}

Solution* Heuristic::prim(vector<Edge*> pool){
	//cout<<"prim..."<<endl;

	Solution *sol = new Solution(instance);
	int n_rand = rand_r(&seed)%pool.size();
	Edge *init = pool.at(n_rand);
	//cout << "choose "<<n_rand<<"-th pool sol"<<endl;

	int *nodes = (int*)malloc(sizeof(int)*instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		nodes[i]=0;
	}
	//init->lock();
	nodes[init->get_i()]=1;
	nodes[init->get_j()]=1;
	sol->add_edge(init);
	Edge *new_edge;
	do{
		new_edge=NULL;
		for(int i=0;i<instance->num_vertex();i++){
			if(sol->has_vertex(i)){
				Edge *best=NULL;
				for(int j=0;j<instance->num_vertex();j++){
					Edge *e = instance->get_edge(i,j);
					if(e!=NULL && !sol->has_vertex(j) && !nodes[j] && !nodes[i]){
						if(best==NULL || e->get_cost()<best->get_cost()){
							best=e;
						}
					}
				}
				if(best!=NULL && (new_edge==NULL || best->get_cost()<new_edge->get_cost())){
					new_edge=best;
				}
			}
		}
		if(new_edge!=NULL){
			if(sol->is_better(new_edge))
				sol->add_edge(new_edge);
			else{
				//new_edge->lock();
				nodes[new_edge->get_i()]=1;
				nodes[new_edge->get_j()]=1;
			}
		}
	}while(new_edge!=NULL);
	//free(nodes);
	//cout<<"ok"<<endl;
	return sol;
}

void Heuristic::best_fit(Solution *sol,vector<Edge*> pool){
	if(pool.size()==0)return;
	vector<Solution*> group;
	for(unsigned int i=0;i<pool.size();i++){
		Solution *s = new Solution(instance);
		s->add_edge(pool.at(i));
		group.push_back(s);
	}
	bool improve=true;
	while(improve){
		cout << "Size: "<<group.size()<<endl;
		improve=false;
		pair<float,vector<Edge*> > diff,best;
		Solution *best_s;
		int indice=-1;
		for(unsigned int i=0;i<group.size();i++){
			diff = sol->diff(group.at(i));

			/*cout << "SOL:" <<endl;
			sol->print();
			cout << "SOL2:" <<endl;
			group.at(i)->print();
			cout <<"diff:"<<endl;
			for(unsigned int k=0;k<diff.second.size();k++){
				cout << (diff.second.at(k)->get_i()+1)<<","<< (diff.second.at(k)->get_j()+1)<<" |";
			}
			cout<<endl;*/

			if(diff.first-group.at(i)->get_cost()+group.at(i)->get_prize()<0 && (indice==-1 || diff.first<best.first)){
				indice=i;
				best=diff;
				best_s=group.at(i);
				improve=true;
				//cout << "best"<<endl;
			}

		}
		if(improve){
			//cout <<"Appling: " <<best.second.size()<<endl;
			sol->apply(best,best_s);
			group.erase(group.begin()+indice);
		}
	}
}

vector<Vertex*> Heuristic::build_random_pool_vertex(unsigned int length){
	cout << "Random pool"<<endl;
	vector<Vertex*> all_vertex;
	for(int i=0;i<instance->num_vertex();i++){
		all_vertex.push_back(instance->get_vertex(i));
	}
	for(unsigned int i=0;i<length;i++){
		int n_rand = rand_r(&seed)%(all_vertex.size()-i);
		Vertex *tmp = all_vertex[n_rand];
		all_vertex[n_rand] = all_vertex[all_vertex.size()-i-1];
		all_vertex[all_vertex.size()-i-1] = tmp;
	}
	vector<Vertex*> pool;
	for(unsigned int i=0;i<length;i++){
		pool.push_back(all_vertex[all_vertex.size()-i-1]);
	}
	return pool;
}

vector<Vertex*> Heuristic::build_pool_vertex(unsigned int length){
	cout << "Heuristic pool"<<endl;
	typedef pair<Vertex*,float> elem;
	vector<elem> t_pool;
	float worst=0;
	int worst_pos=-1;
	for(int i=0;i<instance->num_vertex();i++){
		LocalSol *s = new LocalSol(instance);
		vector<Vertex*> nb = deep_search(s,i,3);
		float prize=0;
		for(unsigned j=0;j<nb.size();j++){
			prize+=nb.at(j)->get_prize();
		}
		float eval = prize;

		if(t_pool.size()<length){
			t_pool.push_back(make_pair(instance->get_vertex(i),eval));
			if(worst_pos==-1 || eval>worst){
				worst=eval;
				worst_pos = t_pool.size()-1;
			}
		}else{
			if(eval>worst){
				worst=eval;
				t_pool.erase(t_pool.begin()+worst_pos);
				t_pool.push_back(make_pair(instance->get_vertex(i),eval));
				worst_pos = t_pool.size()-1;
				for(unsigned j=0;j<t_pool.size();j++){
					if(t_pool.at(j).second<worst){
						worst = t_pool.at(j).second;
						worst_pos=j;
					}
				}
			}
		}
	}
	vector<Vertex*> pool;
	for(unsigned int i=0;i<t_pool.size();i++){
		cout << t_pool.at(i).first->get_id()<<endl;
		pool.push_back(t_pool.at(i).first);
		//cout << (t_pool.at(i).first->get_id()+1)<<":" <<t_pool.at(i).second << endl;
	}
	return pool;
}

vector<Vertex*> Heuristic::deep_search(LocalSol *sol,int v_id,int depth){
	int* visited = (int*) malloc(sizeof(int)*instance->num_vertex());
	for(int i=0;i<instance->num_vertex();i++){
		if(sol->has_vertex(i))
			visited[i]=1;
		else
			visited[i]=0;
	}
	visited[v_id]=1;
	vector<Vertex*> ans = perform_deep_search(visited,v_id,depth);
	ans.push_back(instance->get_vertex(v_id));
	return ans;
}

vector<Vertex*> Heuristic::deep_search(LocalSol *sol,Vertex *v,int depth){
	return deep_search(sol,v->get_id(),depth);
}

vector<Vertex*> Heuristic::perform_deep_search(int *visited,int v_id,int depth){
	vector<Vertex*> ans;
	//cout << "perform"<<endl;
	typedef pair<int,int> elem;
	queue<elem> fila;
	elem e = make_pair(v_id,0);
	fila.push(e);
	while(!fila.empty()){
		e = fila.front();
		fila.pop();
		ans.push_back(instance->get_vertex(e.first));
		//cout << (e.first+1)<<":"<<e.second<<endl;
		if(e.second<depth){
			vector<int> nb = instance->neighborhood(e.first);
			for(unsigned int i=0;i<nb.size();i++){
				int j = nb.at(i);
				if(!visited[j]){
					elem tmp = make_pair(j,e.second+1);
					fila.push(tmp);
					visited[j]=1;
				}
			}
		}
	}
	return ans;
}

LocalSol* Heuristic::construct(vector<Vertex*> pool,int it){
	int *id_nodes = (int*) malloc(sizeof(int)*pool.size());
	for(unsigned int i=0;i<pool.size();i++){
		id_nodes[i]=pool.at(i)->get_id();
	}
	/*for(int i=0;i<instance->num_vertex();i++){
		int current=rand_r(&seed)%(instance->num_vertex()-i);
		int tmp = id_nodes[instance->num_vertex()-i-1];
		id_nodes[instance->num_vertex()-i-1] = id_nodes[current];
		id_nodes[current]=tmp;
	}*/
	int start_node =it%pool.size();//rand_r(&seed)%pool.size();
	int current =start_node;
	LocalSol *sol = new LocalSol(instance);
	sol->add_vertex(id_nodes[current]);

	float gain;
	bool started=false;
	vector<Vertex*> best;
	int v_best;
	//cout << "Start by "<< (id_nodes[current]+1) <<endl;
	do{
		gain=1;
		v_best=-1;
		for(int j=0;j<instance->num_vertex();j++){
			if(!sol->has_vertex(j)){
				if(sol->has_connection(j)){
					vector<Vertex*> tmp = deep_search(sol,j,1);
					LocalSol *s = new LocalSol(instance);
					float prize=instance->get_vertex(j)->get_prize();
					for(unsigned int i=0;i<tmp.size();i++){
						prize+=tmp.at(i)->get_prize();
						s->add_vertex(tmp.at(i));
					}
					/*for(int i=0;i<instance->num_vertex();i++){
						if(sol->has_vertex(i) && !s->has_vertex(i)){
							s->add_vertex(i);
							prize+=instance->get_vertex(i)->get_prize();
						}
					}*/
					//prize = prize-instance->get_total_prize();
					float p_cost = s->prim();
					float my_gain = prize/p_cost;
					if(my_gain>gain){
						gain = my_gain;
						v_best=j;
						best=tmp;
					}
				}
			}
		}
		if(v_best>=0){
			//cout << "Gain:" << gain<<endl;
			for(unsigned int i=0;i<best.size();i++){
				//cout << "Add "<< (best.at(i)->get_id()+1)<<endl;
				sol->add_vertex(best.at(i));
			}
			started=true;
			//sol->print();
			//getchar();
		}else if(!started){
			sol->remove_vertex(id_nodes[current]);
			current=(current+1)%pool.size();
			sol->add_vertex(id_nodes[current]);
			if(current==start_node)
				started=true;
		}
	}while(v_best>=0 || !started);
	return sol;
}

void Heuristic::mylocalsearch(LocalSol** sol){

	float cost = (*sol)->get_cost();
	for(int i=0;i<instance->num_vertex();i++){
		LocalSol *tmp = (*sol)->copy();
		if(tmp->has_vertex(i)){
			tmp->remove_vertex(i);
		}else if(tmp->has_connection(i)){
			tmp->add_vertex(i);
		}
		if(tmp->get_cost()<cost){
			cost = tmp->get_cost();
			*sol = tmp;
		}
	}
}

void Heuristic::localsearch(LocalSol** sol){
	bool local_imp=true;
	while(local_imp){
		local_imp=false;

		for(int i=0;i<instance->num_vertex() && !local_imp;i++){
			LocalSol *tmp = (*sol)->copy();
			if(tmp->has_vertex(i)){
				tmp->remove_vertex(i);
				//cout << "Removeu "<<(i+1)<<endl;
			}else if(tmp->has_connection(i))
				tmp->add_vertex(i);
				//cout << "Add "<<(i+1)<<endl;
			if(tmp->get_cost()<(*sol)->get_cost()){
				cout << "BL: "<< tmp->get_cost()<<endl;
				local_imp=true;
				*sol=tmp;
			}
		}
	}
}

bool Heuristic::include_edge(int id,LocalSol* sol,int* values){
	Edge *e = instance->get_edge(id);
	//return (sol->has_vertex(e->get_i()) || sol->has_vertex(e->get_j())) || (values[e->get_i()]>=0 && values[e->get_j()]>=0);
	return include_vertex(e->get_i(),sol,values) && include_vertex(e->get_j(),sol,values);
}

bool Heuristic::include_vertex(int id,LocalSol* sol,int* values){
	if(sol->has_vertex(id) || values[id]>=0)
		return true;
	vector<int> nb = instance->neighborhood(id);
	for(unsigned int i=0;i<nb.size();i++)
		//if(sol->has_vertex(nb[i])){
		if(values[nb[i]]==1 || values[nb[i]]==0){
			values[id]=2;
			return true;
		}
	return false;
}

float Heuristic::localsearch2(LocalSol* sol,int* values){
	ofstream lp;
	lp.open("lp.in");

	long n=0;

	lp << "Minimize" << endl;
	lp << " obj: ";

	for (long i = 0,count=0; i < instance->num_edge(); i++) {
		if(include_edge(i,sol,values)){
			if(count!=0)lp<< " + ";
			lp <<instance->get_edge(i)->get_cost() <<" y" << (i + 1);
			count++;
		}
	}
	for (long i = 0; i < instance->num_vertex(); i++) {
		//if(include_vertex(i,sol,values)){
			lp <<" + "<< instance->get_vertex(i)->get_prize() <<" x" << (i + 1)<<"";
			//n++;
		//}
		if(include_vertex(i,sol,values)){
			n++;
		}
	}
	lp << endl;
	lp << "Subject To" << endl;
	long sub = 0;

	lp << " c"<<(++sub) <<": ";
	for (long i = 0,count=0; i < instance->num_edge(); i++) {
		if(include_edge(i,sol,values)){
			if(count!=0) lp << " + ";
			lp << "y" << (i + 1);
			count++;
		}
	}
	for (long i = 0; i < instance->num_vertex(); i++) {
		if(include_vertex(i,sol,values)){
			lp << " - ";
			lp << "k" << (i + 1);
		}
	}
	lp<<" = -1"<<endl;

	for (long i = 0; i < instance->num_vertex(); i++) {
		if(include_vertex(i,sol,values)){
			lp << " c"<<(++sub) <<": ";
			vector<int> nbs = instance->neighborhood(i);
			for (unsigned int j = 0; j < nbs.size(); j++) {
				if(include_vertex(nbs[j],sol,values)){
					if(j!=0)lp<< " + ";
					lp<< "y"<<(instance->get_edge(i,nbs[j])->get_id()+1);
				}
			}
			lp << " - k"<<(i+1)<<" >= 0" <<endl;
		}
	}

	for (long i = 0; i < instance->num_vertex(); i++) {
		if(include_vertex(i,sol,values)){
			vector<int> nbs = instance->neighborhood(i);
			for (unsigned int j = 0; j < nbs.size(); j++) {
				if(include_vertex(nbs[j],sol,values)){
					lp << " c"<<(++sub) <<": ";
					lp<< "y"<<(instance->get_edge(i,nbs[j])->get_id()+1)<< " - "<<"k"<<(i+1)<<" <= 0"<<endl;
				}
			}
		}
	}

	for (long i = 0; i < instance->num_vertex(); i++) {
		if(include_vertex(i,sol,values)){
			lp << " c"<<(++sub) <<": ";
			lp << "x"<<(i+1)<<" + k"<<(i+1)<<" = 1 "<<endl;
		}
	}

	for (long i = 0; i < instance->num_vertex(); i++) {
		if(values[i]==1){
			lp << " c"<<(++sub) <<": ";
			lp << "k"<<(i+1)<<" = "<< values[i] <<endl;
		}
	}

	for (long i = 0; i < instance->num_vertex(); i++) {
		if(values[i]==-1){
			lp << " c"<<(++sub) <<": ";
			lp << "k"<<(i+1)<<" = 0" <<endl;

			lp << " c"<<(++sub) <<": ";
			lp << "x"<<(i+1)<<" = 1" <<endl;
		}
	}

	/*vector<vector<Edge*> > cycs = cycles(sol);
	for(unsigned int i=0;i<cycs.size();++i){
		lp << " c"<<(++sub) <<": ";
		for(unsigned int j=0;j<cycs[i].size();++j){
			if(j!=0)lp<< " + ";
			lp<< "y"<<(cycs[i][j]->get_id()+1);
		}
		lp << " <= "<< (cycs[i].size()-1) <<endl;

	}*/

	lp << "Bounds" << endl;
	lp << "General" << endl;
	for (long i = 0; i < instance->num_edge(); i++) {
		if(include_edge(i,sol,values))
			lp << " y" << (i + 1)<<endl;
	}
	for (long i = 0; i < instance->num_vertex(); i++) {
		//if(include_vertex(i,sol,values)){
			lp << " x" << (i + 1)<<endl;
			lp << " k" << (i + 1)<<endl;
		//}
	}
	lp << "Bin" << endl;
	for (long i = 0; i < instance->num_edge(); i++) {
		if(include_edge(i,sol,values))
			lp << " y" << (i + 1)<<endl;
	}
	for (long i = 0; i < instance->num_vertex(); i++) {
		//if(include_vertex(i,sol,values)){
			lp << " x" << (i + 1)<<endl;
			lp << " k" << (i + 1)<<endl;
		//}
	}

	lp << "End" << endl;

	lp.close();

	system("./solve.sh");

	Parser *parser = new Parser("lp.out");

	for(long i=0;i<instance->num_vertex();i++){
		if(sol->has_vertex(i)){
			sol->remove_vertex(i);
		}
	}

	for(long i=0;i<parser->qnt_p();i++){
		long id = parser->get_p(i)-1;
		values[id] = 1;
		sol->add_vertex(id);
	}
	return parser->get_time();
}

vector<vector<Edge*> > Heuristic::cycles(LocalSol *sol){
	vector<vector<Edge*> > cycles;
	bool found=false;
	for(int i=0;!found;i++){
		if(sol->has_vertex(i)){
			found=true;
			vector<int> parents;
			element elem = make_pair(i,parents);

			vector<vector<Edge*> > tmp = cycles_root(sol,i,elem);
			cycles.insert(cycles.end(),tmp.begin(),tmp.end());

			/*for(unsigned int k=0;k<tmp.size();k++){
				cout << "["<< i <<"]Cycle: ";
				for(unsigned int j=0;j<tmp[k].size();j++){
					cout << (tmp[k][j]->get_id()+1) << " ";
				}
				cout << endl;
			}*/
		}
	}
	return cycles;
}

vector<vector<Edge*> > Heuristic::cycles_root(LocalSol *sol,int root,element e){
	vector<vector<Edge*> > ret;
	if(e.first==root && e.second.size()>2){
		e.second.push_back(root);
		vector<Edge*> edges;
		for(unsigned i=1;i<e.second.size();++i){
			edges.push_back(instance->get_edge(e.second[i-1],e.second[i]));
		}
		ret.push_back(edges);
		return ret;
	}
	vector<int>::iterator it;

	vector<int> nb = instance->neighborhood(e.first);
	for(unsigned int i=0;i<nb.size();++i){
		if(sol->has_vertex(nb[i])){
			it = find(e.second.begin()+1,e.second.end(),nb[i]);
			if(it==e.second.end()){
				vector<int> parents(e.second.begin(),e.second.end());
				parents.push_back(e.first);
				vector<vector<Edge*> > tmp = cycles_root(sol,root,make_pair(nb[i],parents));
				ret.insert(ret.end(),tmp.begin(),tmp.end());
			}
		}
	}
	return ret;
}

#define TOTAL_NB 3

void Heuristic::start(int type){
	//cout << "Starting Heuristic ..."<<endl;
	double s_CPU_inicial, s_CPU_final, s_total_inicial, s_total_final;
	Tempo_CPU_Sistema(&s_CPU_inicial, &s_total_inicial);

	LocalSol *best_sol=NULL;
	vector<Vertex*> pool;
	if(type==0)
		pool = build_pool_vertex(10);
	else
		pool = build_random_pool_vertex(10);

	float time_local=0;

	/*LocalSol *ss = new LocalSol(instance);
	ss->add_vertex(0);
	ss->add_vertex(2);
	ss->add_vertex(3);
	int *values_nb = (int*) malloc(sizeof(int)*instance->num_vertex());
	for(int i=0;i<instance->num_vertex();i++)
		if(ss->has_vertex(i))
			values_nb[i]=1;
		else
			values_nb[i]=-1;

	localsearch2(ss,values_nb);


	for(int i=0;i<instance->num_vertex();i++)
		if(values_nb[i]==2)values_nb[i]=0;

	localsearch2(ss,values_nb);

	best_sol=ss;*/

	//best = search(5);

	/*int size=50;

	vector<Edge*> pool=build_pool(size);
	Solution *s1 = prim(pool);
	int limit=size;
	while(limit>0){
		Solution *s2 = prim(pool);
		pair<float,vector<Edge*> >  gap = s1->diff(s2);
		if(gap.first-s2->get_cost()+s2->get_prize()<0){
			s1->apply(gap,s2);
			limit=size;
		//}else if(s2->get_value()<s1->get_value()){
		//	s1=s2;
		}else
			limit--;
	}
	best = s1;

	best_fit(best,pool);
	*/



	/*vector<Edge*> pool=build_pool(10);
	best = prim(pool);*/

	/*for(int i=0;i<1;i++){
		LocalSol *sol = construct(pool,i);
		cout<< "Iteration: "<< (i+1) <<endl;
		sol->print();
		cout<< "===================="<<endl;
		//cout << "Press enter";
		//getchar();
		if(best_sol==NULL || best_sol->get_cost()>sol->get_cost())
			best_sol=sol;
	}
	localsearch2(best_sol);*/



	best_sol = new LocalSol(instance);

	LocalSol *sol=NULL;
	unsigned int pool_id = 0;
	float avg = 0;
	float qnt = 0;
	vector<float> values;
	for(int it=0;pool_id<pool.size();it++){
		//cout << "start it "<<it<<endl;
		sol = construct(pool,pool_id);

		//cout << sol->get_cost()<<endl;

		avg += sol->get_cost();
		qnt++;
		values.push_back(sol->get_cost());

		pool_id++;
		if(sol->get_cost() < best_sol->get_cost())
			best_sol = sol;
	}
	float cost;
	cost = best_sol->get_cost();
	mylocalsearch(&best_sol);
	//cout << best_sol->get_cost()<<endl;
	//cout << best_sol->get_cost()<<endl;
	//localsearch(&best_sol);

	if(qnt>0){
		avg = avg/qnt;
		float sum;
		for(int i=0;i<qnt;i++)
			sum+=(avg-values[i])*(avg-values[i]);
		stddev = sqrt(sum/qnt);
	}

	/*Solution *s1 = new Solution(instance);
	Solution *s2 = new Solution(instance);

	s1->add_edge(instance->get_edge(5,6));
	s2->add_edge(instance->get_edge(0,1));
	//s2->add_edge(instance->get_edge(2,3));
	s1->apply(s1->diff(s2),s2);
	best=s1;
	*/
	/*best=new Solution(instance);
	best->add_edge(instance->get_edge(5,6));
	best->add_edge(instance->get_edge(7,6));
	best->add_edge(instance->get_edge(7,5));*/

	//LocalSol *sol = new LocalSol(instance,best);

	//best_sol->print();
	best = best_sol->get_solution();
	best->print();
	Tempo_CPU_Sistema(&s_CPU_final, &s_total_final);
	time = s_CPU_final - s_CPU_inicial;
	time+=time_local;
	//cout << "LocalSearch time: "<< time_local <<endl;
	//cout << "Ending Heuristic ..."<<endl;
}

Heuristic::~Heuristic() {
	// TODO Auto-generated destructor stub
}
double Heuristic::get_time(){
	return time;
}

Solution* Heuristic::get_best(){
	return best;
}
